

/**
 *  This helper function constructs the Longest Prefix Suffix (LPS) array, which is crucial for the KMP algorithm.
 * @param {string} pattern 
 * @returns {[string]} Longest Prefix Suffix  array 
 */
const buildLPSArray = (pattern) => {
    const lps = new Array(pattern.length).fill(0);
    let length = 0; // length of the previous longest prefix suffix

    let i = 1;
    while (i < pattern.length) {
        if (pattern[i] === pattern[length]) {
            length++;
            lps[i] = length;
            i++;
        } else {
            if (length !== 0) {
                length = lps[length - 1]; // fallback
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }

    return lps;
}

/**
 * KMP Search
 * @param {string} pattern 
 * @param {string} text 
 * @returns {number} the first index where the pattern is found, or -1 if no match exists.
 */
export const KMPSearch = (pattern, text) => {
    if (pattern.length === 0) return 0;

    const lps = buildLPSArray(pattern);
    let i = 0; // index for text
    let j = 0; // index for pattern

    while (i < text.length) {
        if (pattern[j] === text[i]) {
            i++;
            j++;
        }

        if (j === pattern.length) {
            return i - j; // match found at index (i-j)
        } else if (i < text.length && pattern[j] !== text[i]) {
            if (j !== 0) {
                j = lps[j - 1]; // fallback in the pattern
            } else {
                i++; // move to next character in text
            }
        }
    }

    return -1; // no match found
}

/**
 * Calculate the Levenshtein distance between two strings.
 * @param {string} s1 - First string
 * @param {string} s2 - Second string
 * @returns {number} - Levenshtein distance
 */
export const levenshteinDistance = (s1, s2) => {
    const m = s1.length;
    const n = s2.length;

    // Create a 2D array with (m+1) rows and (n+1) columns
    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

    for (let i = 0; i <= m; i++) {
        dp[i][0] = i; // deletion cost
    }

    for (let j = 0; j <= n; j++) {
        dp[0][j] = j; // insertion cost
    }

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (s1[i - 1] === s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1]; // no additional cost
            } else {
                dp[i][j] = 1 + Math.min(
                    dp[i - 1][j],     // deletion
                    dp[i][j - 1],     // insertion
                    dp[i - 1][j - 1]  // substitution
                );
            }
        }
    }

    return dp[m][n];
};
